﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace MapEditor
{
    [Flags]
    public enum mazeSquare : byte
    {
        north = 1,
        south = 2,
        east = 4,
        west = 8,
        start = 16,
        end = 32
    }

    public class MazeGenerator
    {
         const int NORTH = 0;
         const int EAST =  1;
         const int SOUTH = 2;
         const int WEST  = 3;

        static int currentSeed;
        static Random random;
        static mazeSquare[,] output;

        public static mazeSquare[,] generateMaze(int type, int deadEndFrequency, int deadEndLengh, int lengh, int seed)
        {
            random = new Random(seed);
            return switchType(type, deadEndFrequency, deadEndLengh, lengh);
        }

        public static mazeSquare[,] generateMaze(int type, int deadEndFrequency, int deadEndLengh, int lengh)
        {
            random = new Random();
            currentSeed = random.Next();
            Debug.WriteLine(currentSeed);
            return generateMaze(type, deadEndFrequency, deadEndLengh, lengh, currentSeed);
        }

        static mazeSquare[,] switchType(int type, int deadEndFrequency, int deadEndLengh, int lengh)
        {
            switch (type)
            {
                case 0: return monoModule();
                case 1: return river(deadEndFrequency, deadEndLengh, lengh);
                case 2: return maze(deadEndFrequency, deadEndLengh, lengh);
                case 3: return arena(deadEndFrequency, deadEndLengh, lengh);
            }
            return null;
        }

        #region mono-module

        static mazeSquare[,] monoModule()
        {
            mazeSquare[,] output = { { mazeSquare.start | mazeSquare.end } };
            return output;
        }

        #endregion

        #region river

        static Stack<deadend> deadendStack;

        private class deadend
        {
            public Vector2I position;
            public int direction;
            public deadend(Vector2I p, int d) { position = p; direction = d; }
        }

        static mazeSquare[,] river(int deadEndFrequency, int deadEndLengh, int lengh)
        {
            //init tab
            deadendStack = new Stack<deadend>();
            deadEndLengh = lengh * deadEndLengh / 100; // 
            output = new mazeSquare[lengh + 1, lengh + 1];
            for (int i = 0; i < lengh + 1; i++)
                for (int j = 0; j < lengh + 1; j++)
                    output[i, j] = 0;

            Vector2I currentPosition = new Vector2I();
            int direction = random.Next(4); //choix de la direction de la riviére
            switch (direction) 
            {
                case NORTH: currentPosition.set(lengh / 2, lengh    ); break;
                case EAST:  currentPosition.set(0        , lengh / 2); break;
                case SOUTH: currentPosition.set(lengh / 2, 0        ); break;
                case WEST:  currentPosition.set(lengh    , lengh / 2); break;
            }
            output[currentPosition.x, currentPosition.y] = mazeSquare.start;

            Vector2I lastPosition = null;
            Vector2I nextPosition = getMainDirectionPosition(currentPosition, direction);
            for (int i = 0; i < lengh - 1; i++)
            {
                if (lastPosition != null)
                    switch (random.Next(3))
                    {
                        case 0: nextPosition = getMainDirectionPosition (currentPosition,               direction); break;
                        case 1: nextPosition = getLeftDirectionPosition (currentPosition, lastPosition, direction); break;
                        case 2: nextPosition = getRightDirectionPosition(currentPosition, lastPosition, direction); break;
                    }
                try { createLink(currentPosition, nextPosition); }
                catch (IndexOutOfRangeException) 
                { 
                    // cas rare ou le random fait sortir la riviére du tableau, retour sur la main direction
                    nextPosition = getMainDirectionPosition(currentPosition, direction);
                    createLink(currentPosition, nextPosition);
                }
                if (lastPosition != null && random.Next(100) <= deadEndFrequency) // ajout de cul de sac
                {
                    int deadEndDir = (direction + (random.Next(2) == 1 ? 1 : -1)) % 4;
                    if (deadEndDir == -1)
                        deadEndDir = 3;
                    deadendStack.Push(new deadend(currentPosition, deadEndDir));
                }
                lastPosition = currentPosition;
                currentPosition = nextPosition;
            }
            output[currentPosition.x, currentPosition.y] |= mazeSquare.end;

            while (deadendStack.Count != 0)
            {
                int len = deadEndLengh - random.Next(deadEndLengh) + 1; 
                deadend d = deadendStack.Pop();

                Vector2I d_lastPosition = null;
                Vector2I d_nextPosition = getMainDirectionPosition(d.position, d.direction);
                while (len-- > 0)
                {
                    if (d_lastPosition != null)
                        switch (random.Next(3))
                        {
                            case 0: d_nextPosition = getMainDirectionPosition(d.position, d.direction); break;
                            case 1: d_nextPosition = getLeftDirectionPosition(d.position, d_lastPosition, d.direction); break;
                            case 2: d_nextPosition = getRightDirectionPosition(d.position, d_lastPosition, d.direction); break;
                        }
                    try { createLink(d.position, d_nextPosition); }
                    catch (IndexOutOfRangeException) { break; } //si le cul sac sort de la map, on le termine
                    d_lastPosition = d.position;
                    d.position = d_nextPosition;
                }
            }

            return cut(output);
        }

        private static mazeSquare[,] cut(mazeSquare[,] input)
        {
            int minX; int minY; int maxX; int maxY;
            for (minY = 0; minY < input.GetLength(1); minY++)
                for (int x = 0; x < input.GetLength(0); x++)
                    if (input[minY, x] != 0)
                        goto label1;
            label1:
            for (minX = 0; minX < input.GetLength(0); minX++)
                for (int y = 0; y < input.GetLength(1); y++)
                    if (input[y, minX] != 0)
                        goto label2;
            label2:
            for (maxY = input.GetLength(1) - 1; maxY > 0; maxY--)
                for (int x = 0; x < input.GetLength(0); x++)
                    if (input[maxY, x] != 0)
                        goto label3;
            label3:
            for (maxX = input.GetLength(0) - 1; maxX > 0; maxX--)
                for (int y = 0; y < input.GetLength(1); y++)
                    if (input[y, maxX] != 0)
                        goto label4;
            label4:
            mazeSquare[,] output = new mazeSquare[++maxY - minY + 1, ++maxX - minX + 1];
            int outY = 0;
            for (int i = minY; i < maxY; i++)
            {
                int outX = 0;
                for (int j = minX; j < maxX; j++)
                {
                    output[outY, outX] = input[i, j];
                    outX++;
                }
                outY++;
            }

            return output;
        }

        static Vector2I getMainDirectionPosition(Vector2I position, int direction)
        {
            Vector2I outputVector;
            switch (direction)
            {
                case NORTH: outputVector = new Vector2I(position.x    , position.y - 1); break;
                case EAST:  outputVector = new Vector2I(position.x + 1, position.y    ); break;
                case SOUTH: outputVector = new Vector2I(position.x    , position.y + 1); break;
                case WEST:  outputVector = new Vector2I(position.x - 1, position.y    ); break;
                default: throw new Exception("getMainDirectionPosition: input data error");
            }
            return outputVector;
        }

        static Vector2I getRightDirectionPosition(Vector2I position, Vector2I lastPosition, int direction)
        {
            Vector2I outputVector;
            switch ((direction + 1) % 4)
            {
                case NORTH: outputVector = new Vector2I(position.x    , position.y - 1); break;
                case EAST:  outputVector = new Vector2I(position.x + 1, position.y    ); break;
                case SOUTH: outputVector = new Vector2I(position.x    , position.y + 1); break;
                case WEST:  outputVector = new Vector2I(position.x - 1, position.y    ); break;
                default: throw new Exception("getMainDirectionPosition: input data error");
            }
            if (lastPosition == outputVector)
                return getMainDirectionPosition(position, direction);
            return outputVector;
        }

        static Vector2I getLeftDirectionPosition(Vector2I position, Vector2I lastPosition, int direction)
        {
            Vector2I outputVector;
            switch (direction == 0 ? 3 : direction - 1)
            {
                case NORTH: outputVector = new Vector2I(position.x    , position.y - 1); break;
                case EAST:  outputVector = new Vector2I(position.x + 1, position.y    ); break;
                case SOUTH: outputVector = new Vector2I(position.x    , position.y + 1); break;
                case WEST:  outputVector = new Vector2I(position.x - 1, position.y    ); break;
                default: throw new Exception("getMainDirectionPosition: input data error");
            }
            if (lastPosition == outputVector)
                return getMainDirectionPosition(position, direction);
            return outputVector;
        }

        #endregion

        #region maze

        static mazeSquare[,] maze(int deadEndFrequency, int deadEndLengh, int length)
        {
            int max = -1;
            int [,] squareValue = new int[length + 1, length + 1];
            output = new mazeSquare[length + 1, length + 1];
            for (int i = 0; i < length + 1; i++)
                for (int j = 0; j < length + 1; j++)
                {
                    output[i, j] = 0;
                    squareValue[i, j] = ++max;
                }
            Vector2I randPosition = new Vector2I();
            while (max != 0) // tant que toute les case ne sont pas relié
            {
                //random une case et une direction à lier
                randPosition.set(random.Next(length + 1), random.Next(length + 1));
                int randDir = random.Next(4);
                Vector2I squareToLink = getMainDirectionPosition(randPosition, randDir);

                if (squareToLink.x >= 0 && squareToLink.y >= 0 && squareToLink.x <= length && squareToLink.y <= length &&   // si la liason ne sort pas de la map
                    squareValue[randPosition.x, randPosition.y] != squareValue[squareToLink.x, squareToLink.y])             // si les zones ne sont pas encore relié
                {
                    int currentMax = squareValue[randPosition.x, randPosition.y] > squareValue[squareToLink.x, squareToLink.y] ? squareValue[randPosition.x, randPosition.y] : squareValue[squareToLink.x, squareToLink.y];
                    int newValue;
                    if (squareValue[randPosition.x, randPosition.y] < squareValue[squareToLink.x, squareToLink.y])
                    {
                        newValue = squareValue[randPosition.x, randPosition.y];
                        recursSetValue(newValue, squareToLink, squareValue, length, squareValue[squareToLink.x, squareToLink.y]);
                    }
                    else
                    {
                        newValue = squareValue[squareToLink.x, squareToLink.y];
                        recursSetValue(newValue, randPosition, squareValue, length, squareValue[randPosition.x, randPosition.y]);
                    }
                    if (max == currentMax)
                        max = newValue;
                    createLink(randPosition, squareToLink);
                }
            }
            output[0, 0] |= mazeSquare.start;
            output[length, length] |= mazeSquare.end;
            return output;
        }

        static void recursSetValue(int value, Vector2I position, int[,] squareValue, int length, int initialValue)
        {
            squareValue[position.x, position.y] = value;
            if (position.y > 1           && squareValue[position.x, position.y - 1] == initialValue)
                recursSetValue(value, new Vector2I(position.x, position.y - 1), squareValue, length, initialValue);
            if (position.y <= length - 1 && squareValue[position.x, position.y + 1] == initialValue)
                recursSetValue(value, new Vector2I(position.x, position.y + 1), squareValue, length, initialValue);
            if (position.x <= length - 1 && squareValue[position.x + 1, position.y] == initialValue)
                recursSetValue(value, new Vector2I(position.x + 1, position.y), squareValue, length, initialValue);
            if (position.x > 1           && squareValue[position.x - 1, position.y] == initialValue)
                recursSetValue(value, new Vector2I(position.x - 1, position.y), squareValue, length, initialValue);
        }

        #endregion

        #region arena

        static void createSquare(Vector2I origin, int size)
        {
            Vector2I topLeftCorner = new Vector2I(origin - size / 2);
            Vector2I botRightCorner = new Vector2I(origin + size / 2);

            if ((size & 1) == 0)
                size++;

            for (int i = 0; i < size - 1; i++)
            {
                createLink(new Vector2I(topLeftCorner.x + i, topLeftCorner.y), EAST);
                createLink(new Vector2I(topLeftCorner.x, topLeftCorner.y + i), SOUTH);

                createLink(new Vector2I(botRightCorner.x - i, botRightCorner.y), WEST);
                createLink(new Vector2I(botRightCorner.x, botRightCorner.y - i), NORTH);
            }
        }

        static mazeSquare[,] arena(int deadEndFrequency, int deadEndLengh, int lengh)
        {
            output = new mazeSquare[lengh * 2 + 1, lengh * 2 + 1];
            for (int i = 0; i < lengh + 1; i++)
                for (int j = 0; j < lengh + 1; j++)
                    output[i, j] = 0;

            Vector2I origin = new Vector2I(lengh, lengh);
            output[origin.y, origin.x] = mazeSquare.start | mazeSquare.end | mazeSquare.north | mazeSquare.south | mazeSquare.east | mazeSquare.west;
            for (int i = 0; i < lengh - 1; i++)
            {
                createLink(new Vector2I(origin.x + i, origin.y), EAST);
                createLink(new Vector2I(origin.x - i, origin.y), WEST);
                createLink(new Vector2I(origin.x, origin.y + i), SOUTH);
                createLink(new Vector2I(origin.x, origin.y - i), NORTH);
            }

            createSquare(origin, lengh);
            return cut(output);
        }

        #endregion

        static void createLink(Vector2I a, Vector2I b)
        {
            if (b.y - a.y == 1)       // N -> S link
            {
                output[b.x, b.y] |= mazeSquare.north;
                output[a.x, a.y] |= mazeSquare.south;
            }
            else if (b.y - a.y == -1) // S -> N link
            {
                output[b.x, b.y] |= mazeSquare.south; 
                output[a.x, a.y] |= mazeSquare.north;
            }
            else if (b.x - a.x == 1) // O -> E link
            {
                output[b.x, b.y] |= mazeSquare.east;
                output[a.x, a.y] |= mazeSquare.west;
            }
            else if (b.x - a.x == -1) // E -> O link
            {
                output[b.x, b.y] |= mazeSquare.west;
                output[a.x, a.y] |= mazeSquare.east;
            }
            else
                throw new Exception("createLink: input data error");
        }
        static void createLink(Vector2I a, int direction)
        {
            if (direction == NORTH)
            {
                Vector2I b = new Vector2I(a.x, a.y - 1);
                output[b.x, b.y] |= mazeSquare.south;
                output[a.x, a.y] |= mazeSquare.north;
            }
            else if (direction == EAST)
            {
                Vector2I b = new Vector2I(a.x + 1, a.y);
                output[b.x, b.y] |= mazeSquare.east;
                output[a.x, a.y] |= mazeSquare.west;
            }
            else if (direction == SOUTH)
            {
                Vector2I b = new Vector2I(a.x, a.y + 1);
                output[b.x, b.y] |= mazeSquare.north;
                output[a.x, a.y] |= mazeSquare.south;
            }
            else if (direction == WEST)
            {
                Vector2I b = new Vector2I(a.x - 1, a.y);
                output[b.x, b.y] |= mazeSquare.west;
                output[a.x, a.y] |= mazeSquare.east;
            }
            else
                throw new Exception("createLink: input data error");
        }
        static bool isAdjacent(Vector2I a, Vector2I b)
        {
            return (a.x == b.x && (a.y - b.y) * (a.y - b.y) == 1) || (a.y == b.y && (a.x - b.x) * (a.x - b.x) == 1);
        }
    }

}